package hot100;

import java.util.ArrayList;
import java.util.List;

public class spiralOrder {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> ret = new ArrayList<>();
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return ret;
        }
        //总行数和列数
        int rows = matrix.length;
        int cols = matrix[0].length;
        //设置第二张表，记录轨迹
        boolean[][] temp = new boolean[rows][cols];
        int total = rows * cols;
        //当前行数，列数
        int row = 0;
        int col = 0;
        //方向表
        int[][] directions = {{0,1},{1,0},{0,-1},{-1,0}};
        //当前方向
        int directionIndex = 0;

        for(int i = 0;i < total;i++) {
            //添加当前值
            ret.add(matrix[row][col]);
            temp[row][col] = true;
            //下一行/列，判断是否需要换方向
            int nextRow = row + directions[directionIndex][0];
            int nextCol = col + directions[directionIndex][1];
            if(nextRow < 0 || nextRow >= rows ||
                    nextCol < 0 || nextCol >= cols ||
                    temp[nextRow][nextCol]) {
                directionIndex = (directionIndex + 1) % 4;
            }
            row += directions[directionIndex][0];
            col += directions[directionIndex][1];
        }
        return ret;
    }
}
